import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Leetcode658 {

    public static void main(String[] args) {
        System.out.println(findClosestElements(new int[]{0,1,2,2,2,3,6,8,8,9}, 5, 9));
        System.out.println(findClosestElements(new int[]{1,2,5,5,6,6,7,7,8,9}, 7, 7));
        System.out.println(findClosestElements(new int[]{1, 2, 2, 2, 5, 5, 5, 8, 9, 9}, 4, 0));
        System.out.println(findClosestElements(
                new int[]{0, 0, 1, 2, 3, 3, 4, 7, 7, 8},
                3,
                5
        ));
    }

    //滑动区间
    public static List<Integer> findClosestElements(int[] arr, int k, int x) {
        int minDiff = Integer.MAX_VALUE;
        int minDiffIndex = 0;

        int currentDiff = 0;
        for (int i = 0; i < arr.length; i++) {
            if (i < k) {
                currentDiff += Math.abs(arr[i] - x);
                continue;
            }

            if (currentDiff < minDiff) {
                minDiff = currentDiff;
                minDiffIndex = i - k;
            }

            currentDiff = currentDiff - Math.abs(arr[i - k] - x) + Math.abs(arr[i] - x);
        }

        if (currentDiff < minDiff) {
            minDiffIndex = arr.length - k;
        }

        List<Integer> res = new ArrayList<>();
        for (int i = minDiffIndex; i < minDiffIndex + k; i++) {
            res.add(arr[i]);
        }

        return res;
    }
}
